package com.xing.algorithm.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class TwoSum {

    public static int[] twoSum(int[] nums, int target) {
        if(nums.length == 0) {
            return new int[0];
        }

        HashMap<Integer,ArrayList<Integer>> numsmap = new HashMap<Integer,ArrayList<Integer>>();
        for(int i = 0; i < nums.length; i ++) {
            if(!numsmap.containsKey(nums[i])) {
                ArrayList<Integer> ats = new ArrayList<Integer>();
                numsmap.put(nums[i], ats);
            }
            numsmap.get(nums[i]).add(i);
        }

        Arrays.sort(nums);

        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            if(nums[left] + nums[right] == target) {
                ArrayList<Integer> numslist = numsmap.get(nums[left]);
                if(numslist.size() >= 2) {
                    return new int[]{numslist.get(0),numslist.get(1)};
                }else{
                    return new int[]{numsmap.get(nums[left]).get(0), numsmap.get(nums[right]).get(0)};
                }
            }else if(nums[left] + nums[right] > target) {
                right--;
            } else if(nums[left] + nums[right] < target) {
                left++;
            }
        }

        return new int[0];
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0,4,3,0};
        int[] ss = twoSum(nums, 0);
        for (int i = 0; i < ss.length; i++) {
            System.out.println(ss[i]);
        }
    }
}
